Many proofs in mathematics and many algorithms in computer science use logical expressions such as
“IF \(p\) THEN \(q\)” or “IF \(p_1\) AND \(p_2\), THEN \(q_1\) OR \(q_2\)”
It is therefore necessary to know the cases in which these expressions are either TRUE or FALSE: what we refer to as the truth values of such expressions. We discuss these issues in this chapter.
We also investigate the truth value of quantified statements, which are statements which use the logical quantifiers “for every” and “there exists”.
A proposition (or statement) is a declarative sentence which is true or false, but not both. Consider, for example, the following eight sentences:
All of them are propositions except (vii) and (viii). Moreover, (i), (ii), and (vi) are true, whereas, (iii), (iv), and (v) are false.
Many propositions are composite, that is, composed of subpropositions and various connectives discussed subsequently. Such composite propositions are called compound propositions. A proposition is said to be primitive if it cannot be broken down into simpler propositions, that is, if it is not composite.
(a) “Roses are red and violets are blue” is a compound proposition with subpropositions “Roses are red” and “Violets are blue”.
(b) “John is intelligent or studies every night” is a compound proposition with subpropositions “John is intelligent” and “John studies every night”.
(c) The above propositions (i) through (vi) are all primitive propositions; they cannot be broken down into simpler propositions.
This section discusses the three basic logical operations of conjunction, disjunction, and negation which correspond, respectively, to the English words “and”, “or”, and “not”.
Any two propositions can be combined by the word “and” to form a compound proposition called the conjunction of the original propositions. Symbolically,
\(p \wedge q\)
read “\(p\) and \(q\)”, denotes the conjunction of \(p\) and \(q\). Since \(p \wedge q\) is a proposition it has a truth value, and this truth value depends only on the truth values of \(p\) and \(q\). Specifically:
The truth value of \(p \wedge q\) may be defined equivalently by the table in Fig. 10-1(a). Here, the first line is a short way of saying that if \(p\) is true and \(q\) is true, then \(p \wedge q\) is true. The second line says that if \(p\) is true and \(q\) is false, then \(p \wedge q\) is false. And so on. Observe that there are four lines corresponding to the four possible combinations of T and F for the two subpropositions \(p\) and \(q\). Note that \(p \wedge q\) is true only when both \(p\) and \(q\) are true.
| \(p\) | \(q\) | \(p \wedge q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
| \(p\) | \(q\) | \(p \vee q\) |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
| \(p\) | \(\neg p\) |
|---|---|
| T | F |
| F | T |
Consider the following four statements:
(i) Paris is in France and \(2 + 2 = 4\).
(ii) Paris is in England and \(2 + 2 = 4\).
(iii) Paris is in France and \(2 + 2 = 5\).
(iv) Paris is in England and \(2 + 2 = 5\).
Only the first statement is true. Each of the other statements is false since at least one of its sub statements is false.
Any two propositions can be combined by the word “or” to form a compound proposition called the disjunction of the original propositions. Symbolically,
\(p \vee q\)
read “\(p\) or \(q\)”, denotes the disjunction of \(p\) and \(q\). The truth value of \(p \vee q\) depends only on the truth values of \(p\) and \(q\) as follows.
The truth value of \(p \lor q\) may be defined equivalently by the table in Fig. 10-1(b). Observe that \(p \lor q\) is false only in the fourth case when both \(p\) and \(q\) are false.
Consider the following four statements:
(i) Paris is in France or \(2 + 2 = 4\).
(ii) Paris is in France or \(2 + 2 = 5\).
(iii) Paris is in England or \(2 + 2 = 4\).
(iv) Paris is in England or \(2 + 2 = 5\).
Only the last statement (iv) is false. Each of the other statements is true since at least one of its sub statements is true.
Remark: The English word “or” is commonly used in two distinct ways. Sometimes it is used in the sense of “\(p\) or \(q\) or both”, i.e., at least one of the two alternatives occurs, as above, and sometimes it is used in the sense of “\(p\) or \(q\) but not both”, i.e., exactly one of the two alternatives occurs. For example, the sentence “He will go to Harvard or to Yale” uses “or” in the latter sense, called the exclusive disjunction. Unless otherwise stated, “or” shall be used in the former sense. This discussion points out the precision we gain from our symbolic language: \(p \lor q\) is defined by its truth table and always means “\(p\) and/or \(q\).”
Given any proposition \(p\), another proposition, called the negation of \(p\), can be formed by writing “It is not the case that . . . ” or “It is false that . . . ” before \(p\) or, if possible, by inserting in \(p\) the word “not”. Symbolically,
\(\neg p\)
read “not \(p\)”, denotes the negation of \(p\). The truth value of \(\neg p\) depends on the truth value of \(p\) as follows.
The truth value of \(\neg p\) may be defined equivalently by the table in Fig. 10-1(c). Thus the truth value of the negation of \(p\) is always the opposite of the truth value of \(p\).
Consider the following six statements.
(a1) Paris is in France.
(a2) It is not the case that Paris is in France.
(a3) Paris is not in France.
(b1) \(2 + 2 = 5\).
(b2) It is not the case that \(2 + 2 = 5\).
(b3) \(2 + 2 \neq 5\).
Then (a2) and (a3) are each the negation of (a1); and (b2) and (b3) are each the negation of (b1). Since (a1) is true, (a2) and (a3) are false; and since (b1) is false, (b2) and (b3) are true.
Remark: The logical notation for the connectives “and”, “or”, and “not” are not completely standard. For example, some texts use:
Let \(P(p,q,\ldots)\) denote an expression constructed from logical variables \(p,q,\ldots\), which take on the value TRUE (T) or FALSE (F), and the logical connectives \(\wedge\), \(\vee\), and \(\neg\) (and others discussed subsequently). Such an expression \(P(p,q,\ldots)\) will be called a proposition.
The main property of a proposition \(P(p,q,\ldots)\) is that its truth value depends exclusively upon the truth values of its variables, that is, the truth value of a proposition is known once the truth value of each of its variables is known. A simple concise way to show this relationship is through a truth table. We describe a way to obtain such a truth table below.
Consider, for example, the proposition \(\neg (p\wedge \neg q)\). Figure 10-2(a) indicates how the truth table of \(\neg (p\wedge \neg q)\) is constructed. Observe that the first columns of the table are for the variables \(p,q,\ldots\) and that there are enough rows in the table to allow for all possible combinations of T and F for these variables. (For 2 variables, 4 rows are necessary; for 3 variables, 8 rows are necessary; and, in general, for \(n\) variables \(2^{n}\) rows are required.) There is then a column for each “elementary” stage of the construction of the proposition, the truth table at each step being determined from the previous stages by the definitions of the connectives \(\wedge\), \(\vee\), \(\neg\). Finally we obtain the truth value of the proposition, which appears in the last column.
The actual truth table of the proposition \(\neg (p\wedge \neg q)\) is shown in Fig. 10-2(b). It consists precisely of the columns in Fig. 10-2(a) which appear under the variables and under the proposition; the other columns were merely used in the construction of the truth table.
| \(p\) | \(q\) | \(\neg q\) | \(p \wedge \neg q\) | \(\neg (p \wedge \neg q)\) |
|---|---|---|---|---|
| T | T | F | F | T |
| T | F | T | T | F |
| F | T | F | F | T |
| F | F | T | F | T |
| \(p\) | \(q\) | \(\neg (p \wedge \neg q)\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Remark: In order to avoid an excessive number of parentheses, we sometimes adopt an order of precedence for the logical connectives. Specifically:
\(\neg\) has precedence over \(\wedge\) which has precedence over \(\vee\).
For example, \(\neg p\wedge q\) means \((\neg p)\wedge q\) and not \(\neg (p\wedge q)\).
Some propositions \(P(p,q,\ldots)\) contain only T in the last column of their truth tables or, in other words, they are true for any truth values of their variables. Such propositions are called tautologies. Analogously, a proposition \(P(p,q,\ldots)\) is called a contradiction if it contains only F in the last column of its truth table or, in other words, if it is false for any truth values of its variables. For example, the proposition “\(p\) or not \(p\)”, that is, \(p\vee \neg p\), is a tautology, and the proposition “\(p\) and not \(p\)”, that is, \(p\wedge \neg p\), is a contradiction. This is verified by looking at their truth tables in Fig. 10-5. (The truth tables have only two rows since each proposition has only the one variable \(p\).)
| \(p\) | \(\neg p\) | \(p \vee \neg p\) |
|---|---|---|
| T | F | T |
| F | T | T |
| \(p\) | \(\neg p\) | \(p \wedge \neg p\) |
|---|---|---|
| T | F | F |
| F | T | F |
Note that the negation of a tautology is a contradiction since it is always false, and the negation of a contradiction is a tautology since it is always true.